package may.test_5_19;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class TestMain2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int[] arr = new int[n];
            for (int j = 0; j < n;j++) {
                int c = scanner.nextInt();
                arr[j] = c;
            }

            System.out.println(Math.min(result(arr,k + 1),result(arr,k)));
        }
    }
    private static int result(int[] arr,int k) {
        int tmp = k / 2;
        int a = 0;
        int b = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != -1) {
                if(tmp > 0) {
                    a += arr[i];
                    tmp++;
                } else {
                    b += arr[i];
                }
            }
        }
        return Math.max(a,b);
    }
    private static ArrayList<Integer> retmax(int[] arr,int n) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            if(arrayList.size() < n) {
                arrayList.add(i);
            } else if(arr[arrayList.get(0)] < arr[i]) {
                for (int j = 1; j < arrayList.size(); j++) {
                    if(arr[arrayList.get(j)] > arr[i]) {
                        arrayList.set(j,i);
                    }
                    arrayList.set(j - 1,arrayList.get(j));
                }
            }
        }
        return arrayList;
    }
}
